LeetCode-Go/leetcode/0029.Divide-Two-Integers/29. Divide Two Integers.go at master · halfrost/LeetCode-Go · GitHub

Name: LeetCode-Go/leetcode/0029.Divide-Two-Integers/29. Divide Two Integers.go at master · halfrost/LeetCode-Go · GitHub
Rating: 4.6 (6465 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package leetcode

import (
"math"
)

// 解法一 递归版的二分搜索
funcdivide(dividendint, divisorint) int {
sign, res:=-1, 0
// low, high := 0, abs(dividend)
ifdividend==0 {
return0
 }
ifdivisor==1 {
returndividend
 }
ifdividend==math.MinInt32&&divisor==-1 {
returnmath.MaxInt32
 }
ifdividend>0&&divisor>0||dividend<0&&divisor<0 {
sign=1
 }
ifdividend>math.MaxInt32 {
dividend=math.MaxInt32
 }
// 如果把递归改成非递归，可以改成下面这段代码
// for low <= high {
// quotient := low + (high-low)>>1
// if ((quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) <= abs(dividend)) || ((quotient+1)*abs(divisor) >= abs(dividend) && quotient*abs(divisor) < abs(dividend)) {
// if (quotient+1)*abs(divisor) == abs(dividend) {
// res = quotient + 1
// break
// }
// res = quotient
// break
// }
// if (quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) > abs(dividend) {
// high = quotient - 1
// }
// if (quotient+1)*abs(divisor) < abs(dividend) && quotient*abs(divisor) < abs(dividend) {
// low = quotient + 1
// }
// }
res=binarySearchQuotient(0, abs(dividend), abs(divisor), abs(dividend))
ifres>math.MaxInt32 {
returnsign*math.MaxInt32
 }
ifres<math.MinInt32 {
returnsign*math.MinInt32
 }
returnsign*res
}

funcbinarySearchQuotient(low, high, val, dividendint) int {
quotient:=low+ (high-low)>>1
if ((quotient+1)*val>dividend&&quotient*val<=dividend) || ((quotient+1)*val>=dividend&&quotient*val<dividend) {
if (quotient+1)*val==dividend {
returnquotient+1
 }
returnquotient
 }
if (quotient+1)*val>dividend&&quotient*val>dividend {
returnbinarySearchQuotient(low, quotient-1, val, dividend)
 }
if (quotient+1)*val<dividend&&quotient*val<dividend {
returnbinarySearchQuotient(quotient+1, high, val, dividend)
 }
return0
}

// 解法二 非递归版的二分搜索
funcdivide1(dividedint, divisorint) int {
ifdivided==math.MinInt32&&divisor==-1 {
returnmath.MaxInt32
 }
result:=0
sign:=-1
ifdivided>0&&divisor>0||divided<0&&divisor<0 {
sign=1
 }
dvd, dvs:=abs(divided), abs(divisor)
fordvd>=dvs {
temp:=dvs
m:=1
fortemp<<1<=dvd {
temp<<=1
m<<=1
 }
dvd-=temp
result+=m
 }
returnsign*result
}

funcabs(aint) int {
ifa>0 {
returna
 }
return-a
}